import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

//leetcode239 滑动窗口的最大值
public class Solution2 {

    //自定义单调队列,元素从大到小排列
    class MyDeque{
        Deque<Integer> deque = new LinkedList<>();
        //若push进来的val值大于队列入口处的值,则将队列后面的值弹出,
        //直到val值小于等于队列中入口处的值为止
        //这样就能保证单调队列中元素是从大到小的
        public void add(int val){
            while(!deque.isEmpty() && val > deque.getLast()){
                deque.removeLast();//移除队列入口的元素
            }
            deque.add(val);
        }
        //出队列时(进入下一滑动窗口之前),判断要弹出的元素是否等于队列出口元素
        //若相等则弹出
        public void poll(int val){
            if(!deque.isEmpty() && val == deque.peek()){
                deque.poll();
            }
        }
        //获取当前队列中的最大值
        public Integer getMaxValue(){
            return deque.peek();
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> retList = new ArrayList<>();
        //构造单调队列
        MyDeque myDeque = new MyDeque();
        for (int i = 0; i < k; i++) {
            myDeque.add(nums[i]);
        }
        retList.add(myDeque.getMaxValue());
        for(int i = k; i < nums.length; i++){
            myDeque.poll(nums[i - k]);//弹出队头元素(出窗口)
            myDeque.add(nums[i]);//加入队尾元素(入窗口)
            //获取窗口内的最大值
            retList.add(myDeque.getMaxValue());
        }
        int[] ret = new int[retList.size()];
        int m = 0;
        for (Integer integer : retList) {
            ret[m++] = integer;
        }
        return ret;
    }
}
